package com.cet.algorithm.test.链表;

/**
 * @program: cet-practice
 * @description: 反转链表
 * @author: 陈恩涛
 * @create: 2023-05-14 12:06
 **/
public class LC206 {

    /**
     * 反转链表
     * @param head 链表头结点
     * @return 链表头结点
     */
//    public ListNode reverse(ListNode head){
//
//        if (head == null) {
//            return null;
//        }
//
//        ListNode pre = null;
//        ListNode cur = head;
//
//        while (cur != null) {
//            ListNode temp = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = temp;
//        }
//        return  pre;
//    }

    ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    /**
     * 链表中从第left个节点到第right个节点进行翻转
     * @param head 链表头结点
     * @param left 开始翻转的节点数
     * @param right 结束节点数
     * @return head链表头节点
     */
    public ListNode reverseRange(ListNode head, int left, int right) {

        if (head == null) {
            return null;
        }

        ListNode pre = new ListNode(0);

        ListNode p = pre;

        pre.next = head;

        // 头插次数
        int count = right - left;


        // 将pre指针移动到开始反转的节点的前一个节点
        while (left > 1) {
            pre = pre.next;
            left--;
        }

        ListNode cur = pre.next;

        //头插
        while (count > 0) {
            // 记录待移动的节点
            ListNode insertNode = cur.next;

            cur.next = insertNode.next;

            insertNode.next = pre.next;

            pre.next = insertNode;

            count --;
        }



        return  p.next;
    }

}

class Client206{
    public static void main(String[] args) {
        ListNode head = ListNode.init(1, 2, 3, 4, 5);
        LC206 lc206 = new LC206();
        System.out.println(lc206.reverseRange(head, 1, 4));
    }
}
